package com.basic;

import java.util.Scanner;

public class Fibonacci {
	static int[]  flag = new int[40];
	public static void main(String[] args) {
		long x = System.currentTimeMillis();
//		int num1 = 1,num2 = 1,temp;
		int res = fibonacci1(39);
		System.out.println(res);
		long y = System.currentTimeMillis();
		System.out.println(y - x);
//		System.out.println(res%10007);
//		if(num == 1 || num == 2)
//			System.out.println(num);
//		else {
//			for (int i = 3; i <= num; i++) {
//				temp = num1;
//				num1 = num2;
//				num2 = temp;
//				num2 = num1 + num2;
//			}
//			System.out.println(num2%10007);
//		}
	}
	public static int fibonacci1(int n) {
		if(n == 1 || n == 2)
			return 1;
		else {
			return fibonacci1(n - 1) + fibonacci1(n - 2);
		}
	}
	public static int fibonacci(int n) {
		if(n == 1 || n == 2)
			return 1;
		if(flag[n] != 0)
			return flag[n];
		else {
			flag[n] =  fibonacci(n - 1) + fibonacci(n - 2);
		}
		return flag[n];
	}
}
